#include "sort_algorithm.h"
#include <algorithm>

void sort_algorithm::select_sort(std::vector<int> &array)
{
    /* 选择排序算法 */
    int size = 0;
    if ((size = array.size()) == 0) {
        return;
    }

    for (int i = 0; i < size; ++i) {
        int k = i;
        for (int j = i + 1; j < size; ++j) {
            /* 在未排序区间选择最小的值，用k记录下来 */
            if (array[k] > array[j]) {
                k = j;
            }
        }
        /* 将最小的值交换到排序区间的末尾 */
        std::swap(array[k], array[i]);
    }
}

void sort_algorithm::bubble_sort(std::vector<int> &array)
{
    /* 冒泡排序算法 */
    int size = 0;
    if ((size = array.size()) == 0) {
        return;
    }

    for (int i = size - 1; i >= 0; --i) {
        /* 设置一个flag */
        int flag = false;
        /* 每一轮，都将最大的数移到最右边 */
        for (int j = 0; j < i; ++j) {
            if (array[j] > array[j + 1]) {
                std::swap(array[j], array[j + 1]);
                /* 如果当前轮次发生了交换，则设置flag为true */
                flag = true;
            }
        }

        /* 如果flag为false，说明当前轮次没有发生交换，可以直接退出，加快排序 */
        if (flag = false) {
            break;
        }
    }
}

void sort_algorithm::insertion_sort(std::vector<int> &array)
{
    using std::cout;
    int size = 0;
    if ((size = array.size()) == 0) {
        return;
    }

    for (int i = 1; i < size; ++i) {
        int j = i - 1;
        int cur_num = array[i];

        while (j >= 0 && (array[j] > cur_num)) {
            array[j + 1] = array[j];
            --j;
        }
        array[++j] = cur_num;
        // cout << "array[j]: " << array[j] << ", j: " << j << std::endl;
    }
}

int sort_algorithm::partition(std::vector<int> &numbers, int left, int right)
{
    int i = left;
    int j = right;

    while (i < j) {
        /* 在右半区寻找比numbers[left]小的数，交换至左侧 */
        while (i < j && numbers[j] >= numbers[left]) {
            --j;
        }

        /* 在左半区寻找比numbers[left]大的数，交换至右侧 */
        while (i < j && numbers[i] <= numbers[left]) {
            ++i;
        }
        std::swap(numbers[i], numbers[j]);
    }

    std::swap(numbers[i], numbers[left]);

    return i;
}

void sort_algorithm::quick_sort(std::vector<int> &array, int left, int right)
{
    if (left >= right) {
        return;
    }

    int guard = partition(array, left, right);

    quick_sort(array, left, guard - 1);
    quick_sort(array, guard + 1, right);
}

/* size为堆的大小，从节点index开始，从顶至底堆化 */
void sort_algorithm::sift_down(std::vector<int> &nums, int size, int index)
{
    while (true) {
        /* 获取左子节点的下标 */
        int left = index * 2 + 1;
        /* 获取右子节点的下标 */
        int right = index * 2 + 2;
        int parent = index;

        /* 比较左节点和父节点谁更大 */
        if (left < size && nums[left] > nums[parent]) {
            parent = left;
        }

        /* 比较右节点和父节点谁更大 */
        if (right < size && nums[right] > nums[parent]) {
            parent = right;
        }

        /* parent没有变化，则表示不需要堆化了 */
        if (parent == index) {
            break;
        }

        /* 将更大的结点交换到父节点 */
        std::swap(nums[parent], nums[index]);

        index = parent;
    }
}

void sort_algorithm::heap_sort(std::vector<int> &array)
{
    int size = array.size();

    /* 从顶至底建堆 */
    for (int i = size / 2 - 1; i >= 0; i--) {
        sift_down(array, size, i);
    }

    /* 每次将堆顶(最大值)换到已排序序列的最前面，并重新以该节点从顶至底堆化 */
    for (int i = size - 1; i > 0; i--) {
        std::swap(array[0], array[i]);
        sift_down(array, i, 0);
    }
}

void sort_algorithm::merge(std::vector<int> &nums, int left, int mid, int right)
{
    /* 左子区间: [left, mid]；右子区间：[mid, right] */

    /* 临时数组，存放归并结果 */
    std::vector<int> tmp_arr(right - left + 1);

    /* 左子区间的起始下标 */
    int i = left;
    /* 右子区间的起始下标 */
    int j = mid + 1;
    int k = 0;

    /* 每次选择左右区间中最小的数 */
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp_arr[k++] = nums[i++];
        } else {
            tmp_arr[k++] = nums[j++];
        }
    }

    /* 左子区间中剩下的数，全部填充到临时数组里面 */
    while (i <= mid) {
        tmp_arr[k++] = nums[i++];
    }

    /* 右子区间中剩下的数，全部填充到临时数组里面 */
    while (j <= right) {
        tmp_arr[k++] = nums[j++];
    }

    /* 将临时数组中保存的排序结果，重新填回到结果数组里 */
    for (k = 0; k < tmp_arr.size(); k++) {
        nums[left + k] = tmp_arr[k];
    }
}

void sort_algorithm::merge_sort(std::vector<int> &array, int left, int right)
{
    /* 区间长度为0的时候，停止递归 */
    if (left >= right) {
        return;
    }

    int mid = left + (right - left) / 2;
    /* 划分左子区间 */
    merge_sort(array, left, mid);
    /* 划分右子区间 */
    merge_sort(array, mid + 1, right);

    /* 开始合并各个小的数组 */
    merge(array, left, mid, right);
}

void sort_algorithm::bucket_sort(std::vector<int> &nums)
{
    int k = 10;
    std::vector<std::vector<int>> buckets(k);
    for (auto num : nums) {
        buckets[num / 10].push_back(num);
    }

    for (auto &bucket : buckets) {
        if (!bucket.empty()) {
            std::sort(bucket.begin(), bucket.end());
        }
    }

    int i = 0;
    for (auto bucket : buckets) {
        for (auto num : bucket) {
            nums[i++] = num;
        }
        std::cout << std::endl;
    }
}

void sort_algorithm::radix_sort(std::vector<int> &array)
{
    int max_num = *std::max_element(array.cbegin(), array.cend());

    for (int exp = 1; max_num > exp; exp *= 10) {
        std::vector<std::vector<int>> buckets(10);
        for (const int &num : array) {
            buckets[(num / exp) % 10].push_back(num);
        }

        int k = 0;
        for (auto bucket : buckets) {
            for (auto num : bucket) {
                array[k++] = num;
            }
        }
    }
}

int main()
{
    sort_algorithm sort_algo;
    std::vector<int> array = {5, 1, 8, 4, 9, 31, 10, 6, 3, 2, 99, 98, 97, 96, 95, 22};
    std::vector<int> result = {1, 2, 3, 4, 5, 6, 8, 9, 10, 22, 31, 95, 96, 97, 98, 99};
    // sort_algo.quick_sort(array, 0, array.size() - 1);
    // sort_algo.insertion_sort(array);
    // sort_algo.merge_sort(array, 0, array.size() - 1);
    // sort_algo.heap_sort(array);
    sort_algo.radix_sort(array);
    if (array == result) {
        std::cout << "算法正确, ";
    } else {
        std::cout << "算法错误, ";
    }

    sort_algo.printf_array(array);
    return 0;
}